public class Solution3 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,1,1};
        int target = 3;
        System.out.println(findTargetSumWays(nums,target));
    }
    public static int sum;
    public static int ret;
    public static int target;
    public static int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums,0);
        return ret;
    }

    //解法一： 全局sum
    public static void dfs(int[] nums, int pos ) {

        if(pos == nums.length) {
            if(sum == target) {
                ret++;
            }
            return;
        }

        sum += nums[pos];
        dfs(nums, pos + 1);
        sum -= nums[pos];
        sum -= nums[pos];
        dfs(nums, pos + 1);
        sum += nums[pos];
    }

    //解法二: 局部sum
    public static void dfs(int[] nums, int pos,int sum) {

        if(pos == nums.length) {
            if(sum == target) {
                ret++;
            }
            return;
        }
        //加法
        dfs(nums, pos + 1,sum + nums[pos]);
        //减法
        dfs(nums, pos + 1,sum - nums[pos]);
    }
}
